class Solution:
    def generateParenthesis(self, n: int) -> list[str]:
        self.nums = [0,0] # 左括号 右括号的数
        self.n = n
        self.path = []
        self.result = []
        self.backtracking()
        return self.result
    def isValid(self):
        if max(self.nums) > self.n:
            return False
        return self.nums[0] >= self.nums[1]
    def backtracking(self):
        if self.nums[1]==self.n:
            self.result.append(self.path[:])
            return
        if not self.isValid():
            return
        # 要么左要么右
        for i in (0,1):
            self.path.append("()"[i])
            self.nums[i] += 1 

            self.backtracking()
            self.path.pop()
            self.nums[i] -= 1

s = Solution()
s.generateParenthesis(3)